import math
import random
import sys
import numpy as np
import copy
import xlsxwriter
import matplotlib.pyplot as plt
import datetime
import time
import pandas as pd
import xlrd
import openpyxl

class Node():
    def __init__(self):
        self.Num = 0
        self.Name = None
        self.Longitude = 0
        self.Latitude = 0
        self.Demand = 0
        self.Fixed_Cost = 0

class Model():
    def __init__(self):
        self.I = []
        self.J = []
        self.node_num = 0
        self.cost = {}
        self.distance = {}
        self.lamda = []

        self.x_ = [] # 下界函数的x拔 
        self.y_ = []# 下界函数的y拔
        self.z_LR = 0 # 下界函数求出的z

        self.x = []
        self.y = []
        self.z = 0

        self.LB = -float('inf')
        self.UB = float('inf')

        self.t = 1
        self.NonImprCtr = 0
        self.alpha = 2
        self.gama = 20
        self.kappa = 0.00000001 # LB和UB之间的差值
        # self.zeta = 10000 # 最大迭代次数
        self.zeta = 1
        self.UB_x = []
        self.UB_y = []
        self.delta = None

def Node_information(node):
    print('-----')
    print('node_num:',node.Num)
    print('node_name:',node.Name)
    print('node.Longitude:',node.Longitude)
    print('node.Latitude:',node.Latitude)
    print('node.Demand:',node.Demand)
    print('node.Fixed_Cost:',node.Fixed_Cost)

def ReadData(filepath_1,filepath_2,model):
    df_1 = pd.read_excel(filepath_1)
    for i in range(0,df_1.shape[0]):
        node = Node()
        node.Num = i
        node.Name = df_1['Name'][i]
        node.Longitude = df_1['Longitude'][i]
        node.Latitude = df_1['Latitude'][i]
        node.Demand = df_1['Demand'][i]
        node.Fixed_Cost = df_1['Fixed_Cost'][i]
        model.I.append(node)
        model.J.append(node)
        model.node_num = model.node_num + 1

    # for node in model.node_list:
    #     Node_information(node)

    df_2 = pd.read_excel(filepath_2)
    for i in range(0,df_2.shape[0]):
        for j in range(i,df_2.shape[0]):
            model.cost[i,j] = df_2[i][j]
            model.distance[i,j] = model.cost[i,j]*2
            model.cost[j,i] = model.cost[i,j]
            model.distance[j,i] = model.distance[i,j]

def Initialize(model,node_num):
    for i in range(node_num):
        model.x_.append(0)
        model.y_.append([])
        for j in range(node_num):
            model.y_[i].append(0)
        
    # model.x_ = []
    # model.y_ = []
    # print('model.x_:',model.x_)
    # print('model.y_:',model.y_)


    # model.x = copy.deepcopy(model.x_)
    # model.y = copy.deepcopy(model.y_)

    for i in range (node_num):
        model.lamda.append(1000000)

def Show_Results(model):
    print('--------------')
    print('iteration：{0}    LB = {1}         UB = {2}'.format(model.t,model.LB,model.UB))

# LB没问题
def LB(model):

    model.y_ = []
    for i in range(model.node_num):
        model.y_.append([])
        for j in range(model.node_num):
            model.y_[i].append(0)

    beta = []
    for j in range(model.node_num):
        beta_j = 0
        for i in range(model.node_num):
            calculate_beta = \
                min(0, model.I[i].Demand*model.cost[i,j] - model.lamda[i])
            beta_j = beta_j + calculate_beta
        beta.append(beta_j)
        # print('beta',beta)
        if (beta[j] + model.J[j].Fixed_Cost < 0):
            model.x_[j] = 1
            for i in range(model.node_num):
                if (model.I[i].Demand*model.cost[i,j] - model.lamda[i] < 0): # 换成beta_j才对，看注释
                    model.y_[i][j] = 1
                else:
                    model.y_[i][j] = 0
        else:
            model.x_[j] = 0
            for i in range(model.node_num):
                model.y_[i][j] = 0
    # print('beta',beta)
    model.z_LR = 0
    for j in range(model.node_num):
        model.z_LR = model.z_LR + min(0 , beta[j] + model.J[j].Fixed_Cost)
    for i in range(model.node_num):
        model.z_LR = model.z_LR + model.lamda[i]

    # print('-----LB------')
    # print('model.x_ = ',model.x_)
    # print('model.y666_ = ',model.y_)
    # print('model.z_LR = ',model.z_LR)
    return model.x_,model.y_,model.z_LR

def UB(model):
    model.x = copy.deepcopy(model.x_)
    # print('mod/el.x:',model.x)

    model.y = []
    for i in range(model.node_num):
        model.y.append([])
        for j in range(model.node_num):
            model.y[i].append(0)
    # print('model.y : ',model.y)

    # 对于每个开设的工厂，给它分配最近的客户点
    for i in range(model.node_num):
        min_cost = float('inf')
        record_j = 0
        # 遍历所有客户点
        for j in range(model.node_num):
            if(model.x_[j] == 1 and model.cost[i,j] < min_cost):
                min_cost = model.cost[i,j]
                record_j = j
        model.y[i][record_j] = 1
        for j in range(model.node_num):
            if(j != record_j):
                model.y[i][j] = 0
    # print('model.y:',model.y)
    
    model.z = 0
    for j in range(model.node_num):
        model.z = model.z + model.J[j].Fixed_Cost * model.x[j] 
        for i in range(model.node_num):
            # print('model.I[i].Demand = ',model.I[i].Demand)
            # print('model.y[i][j] = ', model.y[i][j])
            model.z = model.z + model.I[i].Demand * model.cost[i,j] * model.y[i][j]
    

    # print('-----UB------')
    # print('model.x = ',model.x)
    # print('model.y = ',model.y)
    # print('model.z = ',model.z)

    return model.x,model.y,model.z


if __name__ == '__main__':
    filepath_1 = r'88node_Node.xlsx'
    filepath_2 = r'88node_Cost.xlsx'
    model = Model()
    ReadData(filepath_1,filepath_2,model)
    Initialize(model,model.node_num)
    # print('model.x_:',model.x_)
    # print('model.y_:',model.y_)
    # print('model.x:',model.x)
    # print('model.y:',model.y)
    # LB(model)
    # UB(model)

    while(1):
        model.x_,model.y_,model.z_LR = LB(model)
        # print('model.y_ = ',model.y_)
        # Show_Results(model)
        if (model.z_LR > model.LB):
            model.LB = model.z_LR
            model.NonImprCtr = 0
        else:
            model.NonImprCtr = model.NonImprCtr + 1
            if (model.NonImprCtr == model.gama):
                model.alpha = model.alpha/2
                model.NonImprCtr = 0
        model.x,model.y,model.z = UB(model)
        # print(model.x)
        # print(model.y)
        # print('model.z_LR ：',model.z_LR )
        if (model.z < model.UB):
            model.UB = model.z
            model.UB_x = copy.deepcopy(model.x)
            model.UB_y = copy.deepcopy(model.y)

        # print(model.y_)

        sum_ij = 0
        for i in range(model.node_num):
            sum_j = 0
            for j in range(model.node_num):
                sum_j = sum_j + (model.y_[i][j])
            sum_ij = sum_ij + (1- sum_j)**2
        # print('sum_ij = ',sum_ij)
        model.delta = (model.alpha*(model.UB - model.z_LR))/sum_ij
        # print('model.delta = ',model.delta)



        # 25
        # print('model.lamda = ',model.lamda)
        for i in range(model.node_num):
            sum_j = 0
            for j in range(model.node_num):
                sum_j = sum_j + model.y_[i][j]
            model.lamda[i] = model.lamda[i] + model.delta*(1 - sum_j)
        model.t = model.t + 1
        # print('model.lamda = ',model.lamda)

        # Show_Results(model)

        # print('model.lamda:',model.lamda)

        # break

        if (model.UB - model.z_LR <= model.kappa or model.t > model.zeta):
            break

    # print('x_UB = ',model.x)
    # print('y_UB = ',model.y)
    # print('UB = ',model.UB)

    
    
    